Concerning the poor efficiency in unknown protocol frame segmentation, an unknown protocol frame segmentation algorithm based on preamble mining was proposed. Firstly, the principle of the preamble being used as the start of frame was introduced. As the cause that the existing frequent sequence mining algorithm cannot mine long preamble directly, the problems in candidate sequence selection were analyzed. Combining with the characteristics of preamble, two methods for selecting candidate sequences from the target bit streams and selecting candidate sequence based on the variation of the size of candidate sequence set were given. Secondly, an algorithm inferring the length of preamble and mining the preamble was put forward for unknown protocol frame segmentation. Finally, experiments were conducted with real bit streams captured from the Ethernet. The experimental results show that the proposed algorithm can rapidly and accurately mine the preamble sequence in the bit stream of the unknown protocol with lower space and time complexity.